package org.cabbage.lintcode;

/**
 * 写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。
 * <p>
 * 这个矩阵具有以下特性：
 * <p>
 * 每行中的整数从左到右是排序的。 每一列的整数从上到下是排序的。 在每一行或每一列中没有重复的整数。
 *
 * @author gezhangyuan
 */
public class SearchMatrix {


    static int count = 0;

    public static void main(String[] args) {
        SearchMatrix sm = new SearchMatrix();
        sm.searchMatrix(new int[][]{new int[]{4},
                new int[]{5}}, 1);
        System.out.println(count);
    }

    public int searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return 0;
        }
        int index = searchTitle(matrix, target, 0, matrix.length - 1);
        for (int i = 0; i <= index; i++) {
            search(matrix[i], target, 0, matrix[i].length - 1);
        }
        return count;
    }

    public int searchTitle(int[][] matrix, int target, int start, int end) {
        int t = (start + end) / 2;
        if (matrix[t][0] == target) {
            return t;
        }
        if (matrix[t][0] > target) {
            if (start == end) {
                return t - 1;
            }
            return searchTitle(matrix, target, start, t == start ? t : t - 1);
        } else {
            if (start == end) {
                return t;
            }
            return searchTitle(matrix, target, t == end ? t : t + 1, end);
        }
    }

    public void search(int[] source, int target, int start, int end) {
        int t = (start + end) / 2;
        if (source[t] == target) {
            count++;
            return;
        }
        if (start != end) {
            if (source[t] > target) {
                search(source, target, start, t == start ? t : t - 1);
            } else {
                search(source, target, t == end ? t : t + 1, end);
            }
        }
    }

}
